package dp;

import java.util.LinkedList;
import java.util.Stack;

//宽度为1，求最大的面积
public class MaxAreaOfRectangle {

	public static void main(String[] args) {
		MaxAreaOfRectangle object = new MaxAreaOfRectangle();
		int[] A = {281,179,386,165,88,500};
		int[] a = {1,2,5,7,4,2};
		System.out.println("res: " + countArea(A));
		System.out.println("res: " + getMaxArea(a));
		System.out.println("res: " + object.maxRectagle(A));
		System.out.println("res：" + object.maxRectagle(a));
	}
	
	//45ms,5000k
	//dp[i][j] 表示从i开始以j结尾时的面积
	//dp[i][j] = dp[i][j - 1] + leftmin (while A[j] > leftMin)
	//leftmin = A[j], dp[i][j] =  ++distance * leftmin (while A[j] < leftMin)
	
	//absolutely, that time complexity is O(n^2), so is the space complexity
    public static int countArea(int[] A) {
    	if(A == null || A.length <= 0){
    		return -1;
    	}
    	int[][] result = new int[A.length][A.length];
    	int leftMin = A[0];  //左边最小的矩形高度
    	int max = 0;  //记录最大面积
    	//初始化边界条件
    	//得到dp[0][j]的值
    	for (int j = 0; j < A.length; j++) {
    		if(A[j] < leftMin){
    			leftMin = A[j];
    		}
			result[0][j] = (j + 1) * leftMin;
			max = Math.max(max, result[0][j]);
		}
		result[result.length - 1][result.length - 1] = A[A.length - 1];
		max = Math.max(max, result[result.length - 1][result.length - 1]);
    	int curMax = 0;
    	int  distance = 0;  //长
    	for (int i = result.length - 2; i >= 1; i--) {
    		System.out.println("i " + i);
    		leftMin = A[i];
    		distance = 0;
    		curMax = 0;
			for (int j = 1; j < result[0].length; j++) {
				if(i > j){
					continue;
				}
				if(A[j] >= leftMin){
					distance ++;
					curMax = result[i][j - 1] + leftMin;
					System.out.println("max from1  " + curMax);
				}else{
					leftMin = A[j];
					curMax = A[j] * ++distance;
					System.out.println("max from2  " + curMax);
				}
				System.out.println(" max :" +result[i + 1][j] + "   " + curMax);
//				result[i][j] = Math.max(result[i + 1][j], curMax);
				result[i][j] = curMax;
				max = Math.max(max, curMax);
			}
		}
    	//用来查看结果
    	for (int i = 0; i < result.length; i++) {
			for (int j = 0; j < result[0].length; j++) {
				System.out.print(" " + result[i][j]);
			}
			System.out.println();
		}
    	return max;
    } 
    
    
    //the O(n) with a stack method ,is amazing
    //http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
    public int getMaxArea(int hist[], int n){
        // Create an empty stack. The stack holds indexes of hist[] array
        // The bars stored in stack are always in increasing order of their
        // heights.
        Stack<Integer> s = new Stack<Integer>();

        int max_area = 0; // Initalize max area
        int tp;  // To store top of stack
        int area_with_top; // To store area with top bar as the smallest bar

        // Run through all bars of given histogram
        int i = 0;
        while (i < n)
        {
            // If this bar is higher than the bar on top stack, push it to stack
            if (s.empty() || hist[s.peek()] <= hist[i])
                s.push(i++);

            // If this bar is lower than top of stack, then calculate area of rectangle 
            // with stack top as the smallest (or minimum height) bar. 'i' is 
            // 'right index' for the top and element before top in stack is 'left index'
            else
            {
                tp = s.peek();  // store the top index
                s.pop();  // pop the top

                // Calculate the area with hist[tp] stack as smallest bar
                area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);

                // update max area, if needed
                if (max_area < area_with_top)
                    max_area = area_with_top;
            }
        }

        // Now pop the remaining bars from stack and calculate area with every
        // popped bar as the smallest bar
        while (s.empty() == false)
        {
            tp = s.peek();
            s.pop();
            area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);

            if (max_area < area_with_top)
                max_area = area_with_top;
        }

        return max_area;
    }
    
    
    //samplify the above code
    public static int getMaxArea(int[] highs){
    	int max = 0, temp = 0, h = 0;
    	LinkedList<Integer> stack = new LinkedList<Integer>();
    	//注意这个循环，里面有一个i--，所以循环的复杂度并不是O(n)
    	for (int i = 0; i <= highs.length; i++) {
    		h = (i == highs.length ? 0 : highs[i]); 
			if(stack.isEmpty() || h >= highs[stack.peek()]){
				stack.push(i);
				System.out.println("push : :" + i);
			}else {
				temp = stack.pop();
				System.out.println("pop : :" + temp + " i: " + i);
				System.out.println("curArea : " + highs[temp] * (stack.isEmpty() ? i : i - 1 - stack.peek()));
				max = Math.max(max, highs[temp] * (stack.isEmpty() ? i : i - stack.peek() - 1));
				i--;
			}
		}
//    	without i-- and more specify
//    	int curMax = 0;
//    	for (int i = 0; i <= highs.length; i++) {
//			while (!stack.isEmpty()
//					&& (i == highs.length || highs[stack.peek()] >= highs[i])) {
//				curMax = (highs[stack.pop()])
//						* (stack.isEmpty() ? i : i - stack.peek() - 1);
//				if (curMax > max)
//					max = curMax;
//			}
//			stack.push(i);
//		}
    	System.out.println(max);
		return max;
    }
    
    
    public static int getMaxArea2(int[] heights){
    	if(heights == null || heights.length <= 0){
    		return -1;
    	}
    	int curMax = 0, max = 0;
    	LinkedList<Integer> stack = new LinkedList<Integer>();
    	for (int i = 0; i <= heights.length; i++) {
    		//之所以要处理i == highs.length的情况是因为可能遍历完整个数组之后，栈中还有元素
    		//在i == highs.length时一并处理，将所有的元素弹出栈
    		//出栈的规则是当前元素小于栈顶的元素时，就一直出栈，直到找到第一个栈中小于该元素或者栈为空
			while (!stack.isEmpty()
					&& (i == heights.length || heights[stack.peek()] >= heights[i])) {
				curMax = (heights[stack.pop()])
						* (stack.isEmpty() ? i : i - stack.peek() - 1);
				if (curMax > max){
					max = curMax;
				}
			}
			//若5当前值比栈顶元素的值要大时，就进栈， 注意进栈的是下标
			stack.push(i);
		}
    	return max;
    }
    
    
    //左程云的书上面的解法
    public int maxRectagle(int[] heights){
    	int curMax = 0, max = 0;
    	LinkedList<Integer> stack = new LinkedList<Integer>();
    	if(heights == null || heights.length <= 0){
    		return 0;
    	}
		for (int i = 0; i < heights.length; i++) {
			// 一旦遇到小于等于栈顶的元素heights[i]，出栈到栈中的元素小于heights[i]
			int index = 0;
			int k = 0;
			while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
				index = stack.pop();
				// index的柱子向左能扩展到哪里呢，假设新的栈顶为k
				// 那么肯定是k + 1
				k = stack.isEmpty() ? -1 : stack.peek();
				System.out.println("the index:" + index + " K: " + k + " i:" + i);
				// 向右最远能扩展到哪儿呢
				// 由于i位置小于等于j位置（否则j位置不会被弹出）
				// 如果i == j位置，也没关系，因为到i位置的时候还会更新
				// 所以现在先算能扩展到i - 1位置
				curMax = (i - 1 - (k + 1) + 1) * heights[index];
				max = Math.max(max, curMax);
				System.out.println("curMax:" + curMax + "max: " + max);
			}
			
			//这一段不能放在while的前面(虽然逻辑在while的前面)，比如1 2 5 4 3，到元素4的时候，如果放在前面，会不执行，
			//然后执行while语句，可是执行完之后，i++了，不会将元素4的下标压进栈
			// 此处的逻辑是如果栈为空或者heights[i]大于栈顶的元素，就入栈
			if (stack.isEmpty() || heights[i] > heights[stack.peek()]) {
				stack.push(i);
			}
		}
		// 由于最后可能还有值没有计算，所以要认为越界之后的值极小，此时将栈中的元素全部出栈
		while (!stack.isEmpty()) {
			int index = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			curMax = (heights.length - 1 - (k + 1) + 1) * heights[index];
			max = Math.max(max, curMax);
		}
    	return max;
    }
}
